package  main.java.leetcode.editor.cn;
//2022-04-10 13:47:13
//给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。 
//
// 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abc"
//输出：3
//解释：三个回文子串: "a", "b", "c"
// 
//
// 示例 2： 
//
// 
//输入：s = "aaa"
//输出：6
//解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 由小写英文字母组成 
// 
//
// 
//
// 注意：本题与主站 647 题相同：https://leetcode-cn.com/problems/palindromic-substrings/ 
// Related Topics 字符串 动态规划 
// 👍 40 👎 0

class A7VOhD {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new A7VOhD().new Solution();
        solution.countSubstrings("aaaaa");
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countSubstrings(String s) {

        boolean[][] dp = new boolean[s.length()][s.length()];

        //初始化dp数组
        for(int i = 0;i<s.length();i++){
            dp[i][i] = true;
        }
        int ans = 0;

        for(int slowIndex = s.length()-2;slowIndex>=0;slowIndex--){
            for(int fastIndex = slowIndex+1;fastIndex<s.length();fastIndex++){
                if(s.charAt(slowIndex) == s.charAt(fastIndex)){
                    if(fastIndex-slowIndex<=1){
                        dp[slowIndex][fastIndex] = true;
                    }
                    if(fastIndex-slowIndex>1){
                        dp[slowIndex][fastIndex] = dp[slowIndex+1][fastIndex-1];
                    }
                }
            }
        }
        for(int i = 0;i<s.length();i++){
            for(int j = i;j<s.length();j++){
                if(dp[i][j] == true){
                    ans += 1;
                }
            }
        }

        return ans;

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
